<!DOCTYPE html>  
<html>
    <meta charset="utf-8" />  
    <title>插入算法</title>  
<body>
    <h1>插入算法</h1>
    <h2>>排序小型数组时，此算法比选择排序和冒泡排序性能要好。</h2>>
    <p>
        插人排序每次排一个数组项，以此方式构建最后的排序数组。
        假定第一项已经排序了，接着， 它和第二项进行比较，
        第二项是应该待在原位还是插到第一项之前呢？这样，头两项就已正确排 序，
        接着和第三项比较（它是该插人到第一、第二还是第三的位置呢？），以此类推。
    </p>
</body>
<script>  
    // const arr = [1,4,5,8,9,2,1,6];
    // Array.prototype.insertionSort = function(){
    //     var len = this.length;
    //     var preIndex, current;
    //     for (var i = 1; i < len; i++) {
    //         preIndex = i - 1;
    //         current = this[i];
    //         while(preIndex >= 0 && this[preIndex] > current) {
    //             this[preIndex+1] = this[preIndex];
    //             preIndex--;
    //         }
    //         this[preIndex+1] = current;
    //     }
    //     return this;
    // }
    
    // console.log(arr.insertionSort())

    const arr=[1,2,6,8,9,4,0,11];
    Array.prototype.insertionSort = function(){
        for(var i=1;i<this.length;i++){
            let preIndex = i-1;
            let current = this[i];
            while(preIndex>=0&&this[preIndex]>current){
                this[preIndex+1] = this[preIndex];
                preIndex--;
            }
            this[preIndex+1] = current
        }
        return this;
    }
    console.log(arr.insertionSort())
</script>  
</html>